#include <bits/stdc++.h>
using namespace std;

/*
1039. 多边形三角剖分的最低得分
已解答
中等
相关标签
premium lock icon
相关企业
提示
你有一个凸的 n 边形，其每个顶点都有一个整数值。给定一个整数数组 values ，其中 values[i] 是第 i 个顶点的值（即 顺时针顺序 ）。

假设将多边形 剖分 为 n - 2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和。

返回 多边形进行三角剖分后可以得到的最低分 。
 

示例 1：



输入：values = [1,2,3]
输出：6
解释：多边形已经三角化，唯一三角形的分数为 6。
示例 2：



输入：values = [3,7,4,5]
输出：144
解释：有两种三角剖分，可能得分分别为：3*7*5 + 4*5*7 = 245，或 3*4*5 + 3*4*7 = 144。最低分数为 144。
示例 3：



输入：values = [1,3,1,4,1,5]
输出：13
解释：最低分数三角剖分的得分情况为 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。
 

提示：

n == values.length
3 <= n <= 50
1 <= values[i] <= 100
*/

// 法一
class Solution {
public:
    int minScoreTriangulation(vector<int>& values) {
        int n = values.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));

        // 从小到大 least >= 3
        for (int len = 3; len <= n; len++) {
            // foreach
            for (int i = 0; i + len <= n; i++) {
                int j = i + len - 1;        // last point
                dp[i][j] = INT_MAX;

                // k 中间点 来分割
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[k] * values[j]);
                }
            }
        }
        return dp[0][n - 1];
    }
};

// 法二
class Solution {
public:
    int minScoreTriangulation(vector<int>& values) {
        int n = values.size();
        // dp[i][j]：顶点i到j组成的多边形的最小剖分得分，初始化为较大值（便于后续取min）
        int dp[n][n];
        memset(dp, 0x3f, sizeof dp);
        
        // 按多边形的"跨度"（j-i+1）从小到大计算，len=2对应跨度为2（i和j相邻）
        for (int len = 2; len <= n; ++len) {
            // 遍历起始顶点i
            for (int i = 0; i < n - 1; ++i) {
                int j = i + len - 1; // 终止顶点j
                if (j >= n) break;   // 避免j越界
                
                // 边界：i和j相邻（跨度2，无中间顶点），无法形成三角形，得分0
                if (j == i + 1) {
                    dp[i][j] = 0;
                    continue;
                }
                
                // 枚举分割点k（i<k<j），计算最小得分
                for (int k = i + 1; k < j; ++k) {
                    // 当前得分 = 左子多边形得分 + 右子多边形得分 + 三角形(i,k,j)的得分
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[j] * values[k]);
                }
            }
        }
        
        // 整个多边形（顶点0到n-1）的最小得分
        return dp[0][n - 1];
    }
};